package wj.d909;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class P2 {

    // tasks[体力，金钱]
    public int solve(int n, int k, int[][] tasks) {
        int[] minPrice = new int[]{Integer.MAX_VALUE};
        backTrack(tasks, 0, n, k, new ArrayList<>(), minPrice);
        return minPrice[0];
    }

    public void backTrack(int[][] tasks, int pos, int n, int k, List<Integer> savedList, int[] minPrice) {
        //选择可行的任务
        if (pos == n) {//没有可行的任务
            int price = 0;
            for (int i = 0; i < n; i++) {
                if (!savedList.contains(i)) {
                    price += tasks[i][1];
                }
            }
            if (minPrice[0] > price) {
                minPrice[0] = price;
            }
        } else {
            for (int i = pos; i < n; i++) {
                int[] task = tasks[i];
                if (task[0] <= k) {
                    savedList.add(i);
                    backTrack(tasks, i + 1, n, k - task[0], savedList, minPrice);
                    savedList.remove(savedList.size() - 1);
                }
                //不执行
                backTrack(tasks, i + 1, n, k, savedList, minPrice);
            }
        }
    }


    public int dp(int n, int k, int[][] tasks) {
        int[][] dp = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            int[] task = tasks[i - 1];
            for (int j = 0; j <= k; j++) {
                if (j < task[0]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - task[0]] + task[1]);
                }
            }
        }
        return Arrays.stream(tasks).mapToInt(task -> task[1]).sum() - dp[n][k];
    }

    public static void main(String[] args) {
        int n = 5, k = 5;
        int[][] tasks = new int[][]{
                {2, 5}, {3, 10}, {1, 10}, {3, 8}, {1, 2}
        };
        int a = new P2().dp(n, k, tasks);
        System.out.println(a);
    }
}
